МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ Курсова робота з дисципліни: “ Паралельні та розподілені обчислення” на тему: «Паралельне виконання операцій множення матриць»  Завдання Розробити структуру та описати процедуру перемноження матриці А (розмірністю n1*n2) на матрицю В (розмірністю n2*n3). Для вибраної структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що задані в таблиці. Розміри матриць: n1 = 200 n2 = 248 n3 = 117 Отже маємо матрицю А(250*56) та матрицю В(56*181) Вираз для структури алгоритму множення матриць: 14b-8b-1b-3b-9b-2b-11b-5b Отриманий набір букв: ЙАКПНОИЧ Декодування отриманого набору букв: Й = 14610 = 1001 0010 А = 2710 = 0001 1011 К = 4710 = 0010 1111 П = 21910 = 1101 1011 Н = 13410= 1000 0110 О = 25010= 1111 1010 И = 9110= 0101 1011 Ч = 4910= 0011 0001 Матриця зв’язків: 1 2 3 4 5 6 7 8  1 0 0 0 1 0 0 1 0  2 0 0 0 1 1 0 1 1  3 0 0 0 0 1 1 1 1  4 1 1 0 0 1 0 1 1  5 1 0 0 0 0 1 1 0  6 1 1 1 1 1 0 1 0  7 0 1 0 1 1 0 0 1  8 0 0 1 1 0 0 0 0  Табл. 1.2. Матриця зв’язків Тип початкового завантаження даних: Type = (0+9+0+9+0+4+8)mod 3 +1 = 1 (спільна пам'ять ) tU =10 tS =1 tP =5 tZ =9 tW tU - час виконання однієї операції множення; tS- час виконання однієї операції сумування; tP- час виконання однієї операції пересилання даних між процесорами; tZ - час виконання операції завантаження одних даних; tW - час виконання операції вивантаження одних даних. Анотація У даній курсовій роботі розроблено алгоритм паралельного перемноження двох матриць назаданій структурі згідно з варіантом завдання. При реалізації алгоритму програми використана технологія MPI. Визначено відсоток послідовної частини алгоритму, час його виконання. Програма написана на мові програмування С++. Зміст ВСТУП 6 1. ТЕОРЕТИЧНИЙ РОЗДІЛ 7 1.1. Масштабування і розподіл підзадач по процесорах 9 2. Аналіз (розробка) граф-схеми виконання алгоритму 11 3. Схема планування обчислень 13 4. Розрахунковий розділ 16 5. Розробка програми 18 Висновки 19 СПИСОК ЛІТЕРАТУРИ. 20 Додаток А. Лістинг програми 21 ВСТУП Паралельні обчислення — це форма обчислень, в яких кілька дій проводяться одночасно. Ґрунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших. Є кілька різних рівнів паралельних обчислень: бітовий, інструкцій, даних та паралелізм задач. Паралельні обчислення застосовуються вже протягом багатьох років, в основному в високопродуктивних обчисленнях. Оскільки споживана потужність (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки, паралельне програмування стає домінуючою парадигмою в комп'ютерній архітектурі, основному в формі багатоядерних процесорів. Паралельні комп'ютери можуть бути грубо класифіковані згідно рівня, на якому апаратне забезпечення підтримує паралелізм: багатоядерність, багатопроцесорність — комп'ютери, що мають багато обчислювальних елементів в межах одної машини, а також кластери, MPP, та ґрід — системи що використовують багато комп'ютерів для роботи над одним завданням. Спеціалізовані паралельні архітектури іноді використовуються поряд з традиційними процесорами, для прискорення особливих задач. Програми для паралельних комп'ютерів писати значно складніше, ніж для послідовних, бо паралелізм додає кілька нових класів потенційних помилок, серед яких є найпоширенішоюстан гонитви. Комунікація, та синхронізація процесів зазвичай одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм. Максимальний можливий приріст продуктивності паралельної програми визначається законом Амдала. 1. ТЕОРЕТИЧНИЙ РОЗДІЛ З визначення операції матричного множення випливає, що обчислення усіх елементів матриці може бути виконано незалежно один від одного. Як результат, можливий підхід для орган...